/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution2 {

//    public class ListNode {
//      int val;
//      ListNode next;
//      ListNode(int x) { val = x; }
//    }

    /**
     * 递归
     */
//    public ListNode removeElements(ListNode head, int val) {
//        while(head.next != null){
//            if(head.val == val){
//                head.val = head.next.val;
//                head.next = head.next.next;
//            }else{
//                removeElements(head.next,val);
//            }
//        }
//        return head;
//    }

    /**
     *虚拟头节点
     */
//    public ListNode removeElements(ListNode head, int val) {
//        ListNode dummyHead = new ListNode(-1);
//        dummyHead.next = head;
//
//        ListNode prev = dummyHead;
//        while (prev.next != null){
//            if(prev.next.val == val){
//                prev.next = prev.next.next;
//            }else {
//                prev = prev.next;
//            }
//        }
//        return dummyHead.next;
//    }

    /**
     * 无虚拟头节点，需要对头节点进行特殊处理
     */
//    public ListNode removeElements(ListNode head, int val) {
//
//        while (head != null && head.val ==val){
//            head = head.next;
//        }
//
//        if(head == null){
//            return null;
//        }
//
//        ListNode prev = head;
//        while (prev.next != null){
//            if(prev.next.val == val){
//                prev.next = prev.next.next;
//            }else {
//                prev = prev.next;
//            }
//        }
//        return head;
//    }

    /**
     * 递归
     */
    public ListNode removeElements(ListNode head, int val) {

        if(head == null){
            return null;
        }

        ListNode res = removeElements(head.next, val);
        if(head.val == val){
            return res;
        }else {
            head.next = res;
            return head;
        }


    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,6,4,5,6};
        ListNode head = new ListNode(arr);
        System.out.println(head);

        ListNode listNode = (new Solution2()).removeElements(head, 6);
        System.out.println(listNode);
    }

}
